1. Field of the Invention
The present invention generally relates to on-line systems and methods for the exchange or allocation of goods or services, and more specifically relates to systems and methods for on-line multi-product, sealed-bid auction and exchange markets.
2. Description of the Related Art
The problem of communication complexity is endemic to trade and resource allocation: any mechanism that promotes gains from trade must elicit sufficient information from participants in order to identify which participants want different items. Reducing the complexity of the information elicited for efficient exchange is among the most important practical problems facing mechanism designers. For example, in the National Resident Matching Program (NRMP), which places doctors into hospital residency programs, for a hospital that interviews fifty candidates in the hopes of employing ten to report its preferences fully, the hospital needs to rank, from most-preferred to-least-preferred, not simply all fifty candidates, but rather all possible subsets of ten or fewer doctors from among the fifty. Such a rank-order list would have approximately 1.3×101° entries! In the completed FCC auction 73, which sold 1090 radio spectrum licenses, a value report for all non-empty collections of licenses is a vector of dimension 21090-1≈1.3×10328. These examples illustrate the lengthy report problem which, for moderate sized applications, renders useless any mechanism requiring full, unstructured reporting of preferences.
There are two conventional approaches to mitigating the lengthy report problem. The first approach simplifies the set of reports to reduce the reporting burden on participants. For example, hospitals in the NRMP report rank order lists of individual candidates together with a number of available positions, rather than lists of sets of candidates. In the example from the preceding paragraph, a list of candidates has a length of only fifty, which is practically manageable, and the NRMP algorithm imputes preferences over sets of candidates to make use of the limited reports. This simplification has performed well enough to be used for a long period of years, partly because it satisfies the important fidelity principle that a simplification should represent actual preferences to a good approximation in a large set of realistic cases. Nevertheless, Internet discussion groups detailing annoying limitations of the NRMP underscore its restrictions on preference reporting.
In mechanism design theory, the term “simplification” refers to a mechanism that is obtained from some original “extended” mechanism by restricting the reports available to participants. In a simplification, it is possible that for some preferences, some profiles of reports that were not Nash equilibria of the original unrestricted mechanism can be Nash equilibria of the simplified mechanism. These additional equilibria may have very different properties from the equilibria of the original mechanism, fundamentally changing the character of the mechanism of the simplification. A simplification is tight if, for a wide set of specifications of preferences of the mechanism participants, all the pure Nash equilibria of the new mechanism are Nash equilibria of the original mechanism. Tightness is an important property of a simplified mechanism because it guarantees that the simplification preserves some key properties of the original mechanism, regardless of the preferences of the participants.
The second pure approach to the lengthy report problem employs a dynamic mechanism with staged reporting of information. Such mechanisms economize reporting by only asking for partial information, which may depend on what has been learned in earlier stages of reporting. Ascending and descending multi-product auctions are dynamic mechanisms of this sort which have been popular for commercial applications. These are typically applied when similar but distinct goods are being sold, such as radio spectrum licenses to use different but nearby frequencies, commodities available at different locations or times, commodities available in different grades or with different amounts of processing or commodities subject to different delivery guarantees or contract terms. When goods are substitutes, modern simultaneous ascending or descending auctions—in which various goods are sold in auctions that take place simultaneously and are linked by so-called “activity rules”—are theoretically well-suited to finding stable allocations or competitive prices. During such auctions, bidders learn about market conditions before making their final bids, which may improve the final allocation compared to the simplest sealed-bid mechanisms.
However, dynamic auctions have important drawbacks. The dynamic auctions that perform well according to economic theory require bidders to make very many bids as prices gradually change, leading to long, slow-running auctions that take many hours, days, weeks or even months to reach a conclusion. Such slow auctions are costly for participants and unworkable for spot markets, such as the hour-ahead markets for electricity, where only minutes are available to find clearing prices. For export applications, finding a convenient hour for real-time bidding by participants living in different time zones can be almost impossible. Moreover, because real auctions cannot use the infinitesimal price increments analyzed in theoretical models, actual dynamic auctions are essentially always inexact in finding market-clearing prices.
According to a theoretical result known as the revelation principle, it is possible to duplicate the outcome of any dynamic mechanism using a sealed-bid mechanism in which participants report preferences just once. The development of such an equivalent sealed-bid mechanism equivalent to the ascending or descending multi-product auction, however, has been blocked because suitably compact means of communicating preferences have not been developed. However, two special characteristics shared by many practical applications suggest the possibility of developing a language to communicate preferences efficiently for a set of important applications in which goods are substitutes.
First, when different versions of a good are substitutable at all for a particular user, the rate of substitution is frequently one-for-one or nearly one-for-one. For example, a cement purchaser may wish to buy some quantity of cement and may be prepared to pay more to a supplier located closer to the point of use while the quantity needed may still be fixed independently of the source; thus, the substitution is one-for one. As another example, a northern California electric utility may purchase power at the Oregon border or from southern California, subject to transmission constraints on each source. In yet another example, a cereal maker may be able to substitute bushels of grain today for bushels tomorrow by storing the grain in a suitable facility or by substituting one type of grain for another up to limits imposed by product specifications. The above examples are examples of substitution by buyers, but a similar structure for substitution is found among sellers, such as when a manufacturer can deliver several versions of the same processed good. In each case, substitution probabilities are typically limited, but when substitution is possible, the substitution typically involves approximately one-for-one substitution among various versions of a good. Because the substitution structure may apply to both buyers and sellers, the substitution structure can be exploited to create systems and methods for auctions-to-buy, auctions-to-sell and exchanges in which there may be both multiple bids to buy and multiple offers to sell.
A second feature for the practical implementation of many auction and exchange mechanisms is that buyers and sellers may frequently find it helpful or necessary to respect integer constraints. Many commodities are most efficiently shipped by the truckload or by the container-load, and even divisible resources such as electrical power may frequently be sold in whole numbers of megawatts. Even when integer constraints are not logically necessary, common practices many make them useful, so a practical resource allocation mechanism respects such integer constraints.
One of the current problems with existing sealed-bid trading mechanisms, including exchanges and auctions, is that in their efforts to simplify the bidding process, only very simple bids may be entered and simple rules applied, drastically limiting the ability of bids to communicate complex preferences. For certain types of transactions, more complex bids or rules may be valuable. A buyer able to meet its need in multiple ways and regarding alternative lots as substitutes benefits from an ability to link bids to make multiple bids and limit the number of bids filled to an adequate set of its bids. A trader who wishes to execute a “swap” transaction by buying one item and selling another, may find the transaction too risky unless it can link its bid-to-buy with its offer-to-sell, so that one is executed only if the other is executed as well. In conventional economic analysis, bids-to-buy and offers-to-sell are both particular instances of offers to trade or “bids,” where the transaction quantities are understood to be positive for buyers and negative for sellers. Under this analysis, the prior two examples are both instances of linkages limiting the net or total volume in several transactions, where bids-to-buy represent positive quantities and bids-to-sell represent negative quantities.
An additional limitation to conventional systems is that systems that do allow complex bids—systems known as combinatorial auctions—determine only “package prices” and not market-clearing item prices for individual items to clear markets. This determination of package prices is because, in some exchange problems, market-clearing prices do not exist. However, individual item prices may be needed for many applications. For example, individual item prices provide a basis for allocation of sales revenue to multiple suppliers. It is possible to limit even complex bids so that market-clearing item prices exist.
Accordingly, the manner in which bides communicate with an auction system is important for the success of multi-product auctions, as bidder preferences, demands and supplies are often complex and difficult to describe using conventional, simple bid interfaces.